//考虑孤立点
树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
//如果建一个正向图，一个反向图那么需要两个h数组,共用e[],ne[],idx void add(int h[],int a,int b)
//有的题目建正向图不满足要求，需要建反向图
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a][b] 存储边a->b//稠密图

(2) 邻接表：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[M], ne[M], idx;//N点数,M边数

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

//相较于邻接表更快
(3) vector<int> mp[N];
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    if (u < v)  mp[u].push_back(v);
    if (u > v)  mp[v].push_back(u); // 一个小优化，只由编号小的节点连接到编号大的节点
}
        

树与图的遍历
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
//每个点遍历一次
(1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心
//容易求得子树节点数目（递归），删除树的一个节点得到的连通分支
//分别是该点左的多颗子树，以及整棵树删除以该点为根节点的子树部分
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}
(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
//还可以加一个表示距离的数组d[N];

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

//成环检测，bfs结束入度不为0的点即为环中点
/*
遍历环
for(int i=1;i<=n;i++){
    if(din[i]==0) continue;
    for(;din[i];i=a[i]){
        ....
        din[i] = 0;
    }
}
*/
拓扑排序 —— 模板题 AcWing 848. 有向图的拓扑序列//宽搜的应用
时间复杂度 O(n+m), nn 表示点数，mm 表示边数

int d[N],q[N],cnt = 1;
// d 代表每个元素的入度
// q是拓扑排序的序列，cnt代表q中有多少个元素
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++,d[b]++;
}

bool topsort()
{
    int hh = 0, tt = -1;//队列指针

    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];//队列中元素依次为拓扑序列

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)//将与j相邻的点i的边删除，即入度--
                q[ ++ tt] = j;//只有入度为0才可以入队，因为没有边可以指向它，不会有反向边
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;//存在返回1
}

//带有距离数组的版本，若有a->b,则有dist[b]=dist[a]+1
//从所有入度为0的点出发出发，求出最长的路径，即为至少要分的层数。
拓扑排序求最长路要求是正权且无环
int dist[N];

bool topsort()
{
    for(int i=1;i<=n;i++)
        if(!d[i])
        {
            q[++tt]=i;
            dist[i]=x;
        }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0)
            {
                q[++tt]=j;
                dist[j]=dist[t]+1;
            }
        }
    }
    if(tt==n-1) return true;
    else return false;
}

或者朴素的拓扑排序之后，通过dp求最长路:maxPath[v]=max{maxPaht[v],maxPath[k]+e[k][v]}
for (int i = 1; i <= n; i ++ ) dist[i] = 1;
for (int i = 0; i < n + m; i ++ )
{
    int j = q[i];
    for (int k = h[j]; ~k; k = ne[k])
        dist[e[k]] = max(dist[e[k]], dist[j] + w[k]);
}


朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路
时间复杂是 O(n^2+m)O(n2+m), nn 表示点数，mm 表示边数//适合稠密图，n^2与m一个量级，邻接矩阵
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

memset(g,0x3f,sizeof(g));
cin >>a>>b>>c;
g[a][b]=min(g[a][b],c);//处理重边

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;


        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}


堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数
//优先队列中有冗余部分，就是
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边，不需要特殊处理重边，因为优先队列
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}


Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路——最多经过 k 条边的最短距离//除非有边数限制否则用spfa
时间复杂度 O(nm)O(nm), nn 表示点数，mm 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
//外层循环循环n次，内层循环循环所有边，满足条件就更新
//如果外层循环k次，得到的是从1号点经过不超过k条边所得到的最短距离
//如果外层循环第n次还更新，那么最短路径有n条边，n+1个点，有两个相同的点，即负环

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    //假如1-...->3——>4,1到3的距离为0x3f，如果3到4的权值为负，那么1到4的距离就会被更新为0x3f减去一个负数
    return dist[n];
}
//当对经过的边数有限制时，加上一个备份数组backup[],遍历所有边之前，memcpy(backup,dist,sizeof(dist));
//因为1->2(1),2->3(1),1->3(3)，求只经过一条边的最短路
//过程中更新了dist[2]=1,那么遍历到2到3这条边时，会更新dist[3]=2,发生“串联”，经过超过一条边
//所以backup[]来保存上一次外层循环dist，保证不会超过边数限制


spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路//所求图中不能有负环
时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;//每个点不一定只入队一次，所以采用循环队列
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;//出队

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
//dist[j]更新只有当dist[t]更新（即变小），那么队列中存储dist[]中变小的量即可
//只有前面的点dist变小，后面的点才可能变小
//其他情况应用spfa也行但可能会被卡（可能为网格图）

spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }//为什么要加入所有点，待思考

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}


floyd算法 —— 模板题 AcWing 854. Floyd求最短路//邻接矩阵存储
时间复杂度是 O(n3)O(n3), nn 表示点数
初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

if(d[a][b]>INF/2) puts("impossible");
else printf("%d\n", d[a][b]);
//同样如果存在负权边那么如果a不能到达b，可能d[a][b]的值会小于INF


朴素版prim算法 —— 模板题 AcWing 858. Prim算法求最小生成树//稠密图，记得处理重边，选更小的一条
//生成树是没有自环的
时间复杂度是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
//找到集合中距离最近的点t，用它更新其他点到集合的距离
//与Dij类似
int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

堆优化版prim算法，时间复杂度为O（mlogn）//稀疏图

Kruskal算法 —— 模板题 AcWing 859. Kruskal算法求最小生成树//稀疏图
时间复杂度是 O(mlogm)O(mlogm), nn 表示点数，mm 表示边数
int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];//只需要存储边，不需要复杂的数据结构

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);//路径压缩
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);//将自身编号赋值为祖宗结点的编号
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}


染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图
时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数
//一个图为二分图当且仅当图中不含奇数环
int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}


匈牙利算法 —— 模板题 AcWing 861. 二分图的最大匹配
最坏时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
//第一个集合中元素依次匹配的过程中，如果遇到已经被匹配的第二个集合元素，就看这个元素能否被其他第一个集合元素匹配（递归）
int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))//第二个集合中的点没有匹配或者可以找到另一个点
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}

tarjan算法（强连通分量算法）
int n,m;
int e[N],ne[N],h[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;//栈
bool in_stk[N];//是否在栈中的标记
int id[N],scc_cnt,Size[N];//id[]点对应第几个连通分量,scc_cnt连通分量个数,Size[]第几个连通分量中有多少个点
int dout[N];//出度

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }

    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            Size[scc_cnt]++;
        }while(y!=u);
    }
}

for(int i=1;i<=n;i++)
{
    if(!dfn[i])
        tarjan(i);
}

